package com.suanfa.matrix;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * XO矩阵， 将被X包围的O替换成X
 */
public class XOMatrix {

    public static void main(String[] args) {
        char[][] ch = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};

        solve1(ch);
        System.out.println(JSON.toJSONString(ch));
    }


    public static void solve1(char[][] board){
        int m = board.length;
        int n = board[0].length;

        if(m<3 && n < 3){
            return;
        }

        //从边界元素开始标记O
        for(int i =0; i< m; i++){
            for(int j = 0; j<n; j++){
                if(i == 0||i==m-1||j==0||j==n-1){
                    if(board[i][j] == 'O'){
                        dfs(board, i, j);
                    }
                }
            }
        }

        for(int i =0; i< m; i++){
            for(int j = 0; j<n; j++){
                if(board[i][j]=='A') {
                    board[i][j] = 'O';
                }else if(board[i][j]=='O') {
                    board[i][j] = 'X';
                }
            }
        }


    }



    //类比岛屿搜索，通过dfs将岛屿坐标遍历出来

    public static void dfs(char[][] board, int r, int c){
        if(!inArea(board, r, c)){
            return;
        }
        if(board[r][c] !='O'){
            return;
        }

        board[r][c] = 'A';
        dfs(board, r-1, c);
        dfs(board, r, c+1);
        dfs(board, r+1, c);
        dfs(board, r, c-1);
    }



    public static boolean inArea(char[][] arr, int r, int c){
        return c>=0 && r>=0 && r< arr.length && c< arr[0].length;
    }










    public static void solve(char[][] board){
        int m= board.length;
        int n = board[0].length;
        if(m<3 || n<3){
            return;
        }
        int[][] record = new int[m][n];
        List<List<int[]>> result = new ArrayList<>();
        for(int i=1; i< m; i++){
            for(int j = 1; j< n; j++){
                if(board[i][j] == 'O' && record[i][j] == 0){
                    List<int[]> list = new ArrayList<>();
                    parse(board, i, j, record, list);
                    if(list.size()>0){
                        result.add(list);
                    }
                }
            }
        }
        result.forEach(item->{
            item.forEach(ll->{
                board[ll[0]][ll[1]] = 'X';
            });
        });
    }


    //类比岛屿搜索，通过dfs将岛屿坐标遍历出来

    public static void parse(char[][] board, int r, int c, int[][] record,
                             List<int[]> list){
        if(!inArea(board, r, c)){
            return;
        }
        if(board[r][c] == 'X' || record[r][c] == 1){
            return;
        }
        //有边界元素，无法被包围
        if(r==0 || c == 0 || r == board.length-1 || c == board[0].length-1){
            list.clear();
            return;
        }
        record[r][c] = 1;
        list.add(new int[]{r,c});
        parse(board, r-1, c, record, list);
        parse(board, r, c+1, record, list);
        parse(board, r+1, c,record, list);
        parse(board, r, c-1,record, list);

    }



}
